package Hot100;

public class 搜索二维矩阵 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int up = 0, down = matrix.length - 1;
        while (up <= down) {
            int mid = up + (down - up) / 2;
            if (matrix[mid][0] < target) up = mid + 1;
            else if (matrix[mid][0] > target) down = mid - 1;
            else return true;
        }
        if (down < 0) return false;
        int left = 0, right = matrix[down].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[down][mid] < target) left = mid + 1;
            else if (matrix[down][mid] > target) right = mid - 1;
            else return true;
        }
        return false;
    }
}
